package com.qying.sort;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = Number.arr;

        for (int i : arr) {
            System.out.print(i + ",");
        }
        System.out.println();

        int temp,gap = arr.length /2;
        while (gap > 0 ) {
            for (int i = gap; i < arr.length ; i ++) {

                temp = arr[i];
                int preIndex = i-gap;
                while (preIndex >= 0 && temp > arr[preIndex]) {
                    arr[preIndex +gap] = arr[preIndex];
                    preIndex -= gap;
                }

                arr[preIndex + gap] = temp;
            }

            gap /=2;
        }

        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

}
